//给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
//
//
//
// 示例 1:
//
//
//输入: s = "abcabcbb"
//输出: 3
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//
//
// 示例 2:
//
//
//输入: s = "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
//
//
// 示例 3:
//
//
//输入: s = "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
//
//
//
//
// 提示：
//
//
// 0 <= s.length <= 5 * 10⁴
// s 由英文字母、数字、符号和空格组成
//
//
// Related Topics 哈希表 字符串 滑动窗口 👍 11002 👎 0
import enums.Way;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.HashSet;

/**
 * 无重复字符的最长子串
 */
public class LengthOfLongestSubstring {
    public static int lengthOfLongestSubstring(String s, Way way) {
        switch (way){
            case WAY1:
                return way1(s);
            case WAY2:
                return way2(s);
            case WAY3:
                return way3(s);
            case WAY4:
                return way4(s);
            default:
                throw new IllegalArgumentException("Way is not exist.");
        }
    }

    /**
     * 暴力搜索
     * 时间复杂度：O(n²)
     * 空间复杂度：O(min(m, n))
     */
    private static int way1(String s){
        int length = s.length();
        Set<Character> hashSet = new HashSet<>();
        int maxLength = 0;
        for (int i = 0; i < length; i++){
            for (int j = i; j < length; j++){
                if (hashSet.contains(s.charAt(j))){
                    break;
                }else {
                    hashSet.add(s.charAt(j));
                }
            }
            maxLength = Math.max(maxLength, hashSet.size());
            hashSet.clear();
        }
        return maxLength;
    }

    /**
     * 固定左端点的滑动窗口，以窗口左边第一个元素开始计算最长子串的长度
     * 时间复杂度：O(n)
     * 空间复杂度：O(min(m, n))
     */
    private static int way2(String s){
        int length = s.length();
        Set<Character> hashSet = new HashSet<>();
        int right = -1,maxLength = 0;
        for (int i = 0; i < length; i++) {
            if (i != 0){
                hashSet.remove(s.charAt(i - 1));
            }
            while (right + 1 < length && !hashSet.contains(s.charAt(right + 1))){
                hashSet.add(s.charAt(right + 1));
                right++;
            }
            maxLength = Math.max(maxLength, right - i + 1);
        }
        return maxLength;
    }
    /**
     * 动态滑动窗口，计算窗口内最长子串的长度，重复后从左边开始把元素去除，直到去除到重复元素后重新滑动窗口
     * 时间复杂度：O(n)
     * 空间复杂度：O(min(m, n))
     * 实际使用会比固定左端点的滑动窗口快一点
     */
    private static int way3(String s){
        int length = s.length();
        int left = 0,right = 0;
        int maxLength = 0;
        Set<Character> hashSet = new HashSet<>();
        for (;right < length;right++){
            char c = s.charAt(right);
            while (hashSet.contains(c)){
                hashSet.remove(s.charAt(left));
                left++;
            }
            hashSet.add(c);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    /**
     * 动态滑动窗口，使用Map优化，直接跳过重复元素，不做remove
     * 时间复杂度：O(n)
     * 空间复杂度：O(min(m, n))
     * 由于跳过重复元素不做remove，速度会更快一点
     */
    private static int way4(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, maxLength = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                left = Math.max(left, map.get(c) + 1);
            }
            map.put(c, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}
